7.1 查找的基本概念

 查找表并不是指某一种特定的数据结构，而是被查找的数据的一个称呼

• 静态查找表：仅查找
• 动态查找表：查找、插入与删除


7.2 顺序与折半查找

7.2.1 顺序查找（线性查找）

从头找到尾 

添加哨兵： 


使用顺序表优化


7.2.2 二分查找（折半查找）

仅适用于有序顺序表，链表是不可能实现折半的    


代码实现


效率分析（判定树）

 

 


7.2.3 分块查找（索引顺序查找）

使用存储着每个区间最大值的索引表

 

可以结合折半查找，在这里就和普通的折半查找不同。  移动后是这样的，正常应该是结束查找。但是应在low中查找。 


ASL分析

在索引表顺序查找的情况下：手动模拟一遍就行 在索引表折半查找的情况下：同上，但是注意折半的规律 对于查找失败的情况更加复杂，一般不考

但是，查找表分块有规律： 


7.3 树型查找

7.3.1 二叉排序树（BST）

 

查找

递归的实现方式会导致每一次递归在函数调用栈中新增一个任务，这导致O(h)的空间复杂度。 

插入

递归实现： 

构造


删除

1. 叶子结点：直接删除
2. 只有左或右子树：使用其子树代替 
3. 同时具有左子树右子树：将左子树中的最大值（右子树中的最小值）取出，作为代替结点，被取出的结点的视为被删除，使用操作2. 

ASL

• 成功：时间复杂度O(h)，应该尽可能的保证树的高度最低（平衡）  （1 * 1+2 * 2+3 * 4+4 * 1）/8=2.625

• 失败： 

7.3.2 平衡二叉树（AVL）

树上的任意结点的平衡因子（左子树高 - 右子树高）为-1、0、1。也就是，左右子树的高度不能超过1 

插入后调整树结构

每次调整最小不平衡子树，调整完毕后，其余的节点的平衡因子会自动的恢复正常： 

调整分为四种情况：

1. LL：在结点的左孩子的左子树中插入导致不平衡  这里的所有子树的高度均为H，是因为只有在这种情况下插入节点才会导致A树成为最小不平衡子树。

2. RR：在结点的右孩子的右子树中插入导致不平衡 

3. LR：在结点的左孩子的右子树中插入导致不平衡  无论是插进入C的左边还是右边，都先C左旋，再将C右旋 

其实不必一步步旋转，可以看做是对60结点的一个“提升” 

4. RL：在结点的右孩子的左子树中插入导致不平衡 

代码实现


ASL


删除

时间复杂度：O(log n)

1. 删除结点，与二叉树一样。
2. 向上寻找到最小不平衡子树，找不到就结束。
3. 寻找最小不平衡子树根节的最高点子树，在此子树上重复一次操作，也就是找到个头最高的儿子，与这个儿子的最高的孙子。若果左右儿子、与左右孙子一样，可以随便选一个，结果一样。（在考试中，不可能考多可能性的）
4. 根据孙子与祖先的位置关系，对儿子按LL、RR、RL与LR进行旋转，与插入的操作一样。  
5. 如果有不平衡的现象，重复2操作。（408考察可能性较低）  发生了不平衡传到：  重复步骤2：   不平衡传导结束，算法结束。

7.3.3 红黑树（RBT）

在平衡二叉树（AVL）中进行删除操作，可能会破坏平衡，需要频繁地进行树的形态调整，时间开销大。 而红黑树（RBT），很多时候不会被破坏平衡性，就算需要调整，也可以在常数级的时间内完成。

在经常查询的场景可以使用平衡二叉树，在频繁删除插入的场景使用红黑树。在现代开发过程中，最常使用RBT。

RBT本身是一种优化的BST  左根右，根叶黑，不红红，黑路同 

性质

1. 从根节点到叶结点的最长路径不大于最短路径的2倍
2. 内部有n个节点的RBT的高度h<=2log（n+1）  黑高h，内部结点至少有2^h -1 个  树高h，根结点黑高>=h/2，此时内部最少的结点数为h^(h/2) - 1，也就是n>=h^(h/2) - 1得到h<=2log（n+1）

查找

与BST相同

插入


例子：每次插入不会破坏左根右，根叶黑与黑路同，但只要有不红红，就要调整树的结构。 


删除

• 时间复杂度：O(log 2)
• 与二叉排序树相同
• 在破坏特性后，按找与插入相同的操作

7.4 B、B+树

7.4.1 B树（多路平衡查找树）


查找效率的保证

  在特殊情况下，比如一个元素，根结点就可能不满足有m/2向上取整个分叉。保证树不会太高。  保证树的平衡

满足分叉与关键字数量、平衡要求的多叉树，就是B树。  

特性

 

插入

每次插入终端结点 


 


将提升的结点放置到，其父节点的分叉的后面： 

分裂后再分裂：  


删除

1. 终端结点且满足数量下限：直接删除
2. 根结点：寻找直接前驱或者直接后继代替且满足数量下限（与二叉排序树一样）。转换为了删除终端结点1操作。
3. 不满足数量下限：
   1. 借兄弟：
   2. 兄弟不够：

7.4.2 B+树

与分块查找类似 

 这里的非叶根结点，指不是第一种情况的根节点，即不同时是叶与根的根节点。这是为了保证绝对的平衡。

查找

 也可以使用p指针来顺序查找。

与B树的区别

1. B+树n个结点对应n个分叉，B树n+1个
2. m阶B+树根节点可以取[1,m]，其他结点[m/2向上取整，m]，m阶B树根节点可以取[1,m-1]，其他结点[m/2向上取整-1，m-1]
3. B+树中，叶子结点包含全部的结点，并且内部结点可能重复，B树中各个节点是不重复的。
4. 在B+树中，非叶子结点仅起到索引的作用，只有叶子节点的指针指向记录，B树中的结点包含记录  无论B+树还是B树，其中的每一个结点都存放在一个硬盘的一个一个块中，尽可能的使结点中的关键字数量更多，就能使OS的读取效率更高，度磁盘的次数更少，速度更快。

7.5 散列表（哈希表 Hash）

7.5.1 基本概念



7.5.2 散列函数的构造

在构造的过程中要尽可能的减少冲突的发生。

关键点

1. 定义域要涵盖所有可能出现的关键字
2. 值域不能超过散列表的合法地址范围
3. 散列函数计算出的地址应该尽可能的均匀分布在整个散列表的地址空间，以减少冲突的发生
4. 函数尽可能简单，提高计算效率

除留余数法

场景：通用方法



直接定值法

场景：关键字基本连续分布


数字分析法

场景：关键字集合已知，且某几个数分布均匀


平方取中法

场景：关键字的每一位的取值都不均匀


7.5.3 冲突处理

拉链法

将同义词存储在一个链表中 

查找： 

开放定值法

如果发生冲突，就寻找一个新的空闲位置。 

 d0的值为0，表示初始地址。0 <= i <= m-1

探测序列

1. 线性探测法： 

2. 平方探测法 

3. 双散列法 

4. 伪随机序列法：人为手动提前编写伪随机序列

删除

如果散列表中有大量的已经删除的数据，会导致散列表看起来很满，但是实际很空的问题，导致查找的效率低下。可以不定期的整理散列表来避免。

7.5.4 ASL



找到第一个空位所需要的匹配次数： 

要以散列函数能够覆盖的地址的 长度为分母计算： 

 失败的结果与（2）相同，成功的值的分母-1

装填因子

 

聚集（堆积）

在处理冲突的过程中，不同的初始散列地址的元素争夺同一个位置

  

可以采用平方探测法来减少聚集现象：